/* This file contains structures for building a cfg */
struct CFG *cfg;
struct CFG *cfg2;
struct nodeList *nodeList;
struct BBList *bbList;

#define MAX_VARIABLES 10000
#define MAX_EXPR_DEPTH 50
#define MAX_PARENTS 50

struct gtempTbl{
	int type; /*0 for replacing line with tempKey 
		    1 for replacing val with tempKey */
	int line;
	int val;
	int tempKey;
	char * tempVar;
	struct gtempTbl * next;
};

struct CFG {
	struct BB* entry;
	struct BB* exit;
};

struct NVG {
	int lhs;
	int rhs;
	int constant;
	struct NVG * next;
};

struct nvgOperand {
	int isConst;
	int opConst;
	int opValue;
};

struct replaceTable {
	int del;
	int replace;
	struct replaceTable *next;
};

#define BB_TYPE_DEFAULT 	0
#define BB_TYPE_WHILE_COND 	1
#define BB_TYPE_WHILE_BODY 	2
struct BB {
	struct Three_AddressNode * entry;
	struct Three_AddressNode * exit;
	struct parentBB *parents;
	struct NVG * nvg;
	int marked;
	int parentCount;
	int number;
	struct replaceTable *replace;
	struct expression_tan *exprList;
	int type;
};

struct BBList {
	struct BB *bb;
	struct BBList *next;
};

struct nodeList {
	struct Three_AddressNode *node;
	struct nodeList *next;
};

struct parentBB {
	struct BB* parent;
	struct parentBB* nextparent;
};

#define THREE_ADDRESS_ASSIGN	1
#define THREE_ADDRESS_IF 	2
#define THREE_ADDRESS_WHILE 	3
#define THREE_ADDRESS_DUMMY 	4
struct Three_AddressNode {
	int type;
	// ASSIGN, IF, WHILE, DUMMY
	int LHS;
	int operand1;
	int operand2;
	int operator;
	struct Three_AddressNode* next; // internal
	struct expression_tan* expr;
	struct BB* ptr1;
	struct BB* ptr2;
	struct BB* parent;
	int delFlag;
	int lineNumber;
};

struct expression_tan {
	char *expr;
	int LHS;
	int hash;
	int countRHS;
	int RHS[MAX_EXPR_DEPTH];
	int Lines[MAX_PARENTS];
	int countLines;
	struct expression_tan *next;
};

/* function declarations */

/* CFG Building functions */
void add_block();
void add_to_cfg (struct Three_AddressNode *newNode);
void assign_statement_cfg(struct assignment_statement_t *assignStmt);
void build_cfg(struct program_t *p);
void class_cfg(struct class_list_t *class);
void if_statement_cfg(struct if_statement_t *ifStmt);
void statement_cfg(struct statement_t *stmt);
void statement_sequence_cfg(struct statement_sequence_t *ss);
void while_statement_cfg(struct while_statement_t *whileStmt);
struct Three_AddressNode *add_ThreeAddress(int type, int LHS, int operand1, int operand2, int operator, char *expr, int exprHash);
void add_parent (struct BB *child, struct BB *parent);
int getConstKey(int constant);
void remove_block_from_list(struct BB *bb);
void add_to_bb_list(struct BB *bb);
void remove_from_node_list (struct Three_AddressNode *node);
void add_to_node_list (struct Three_AddressNode *node);

/* Expression Evaluation functions */
char *next_term();
int evaluate_simple_expression(struct simple_expression_t *se);
int evaluate_expression(struct expression_t *exp);
int evaluate_primary(struct primary_t *p);
int evaluate_factor(struct factor_t *f);
int evaluate_term(struct term_t *term);

/* Printing CFG */
void print_cfg(struct CFG * cfg);
void print_block(struct BB * bb);
struct BB * print_blocks(struct BB * bb, int force);
void print_three_address(struct Three_AddressNode *currentNode); 
char *convert_operator(int operator);
void print_tabs_cfg(); 
void print_all_nodes(); 
void print_three_address_final(int line, struct Three_AddressNode *node);

/* nvg functions */
void value_numbering (struct CFG * cfg, int extended);
void reinitialize_mark (struct BB *block);
void remove_replacement (struct BB *bb, int del);
void add_to_replace (struct BB *bb, int del, int rel);
struct replaceTable *lookupReplacement(struct BB *bb, int del);
void nvg_evaluate_block(struct BB *bb);
struct nvgOperand *getOperand(int operand, struct BB *bb, struct Three_AddressNode *node);
int evaluate_const_operation(int const1, int const2, int operator);
int evaluate_non_const_operation(int val1, int val2, int operator);
struct nvgOperand *nvg_evaluate_two_operands(struct nvgOperand *op1, struct nvgOperand *op2, struct Three_AddressNode *node);
struct nvgOperand *nvg_evaluate_operand1(struct nvgOperand *op);
struct nvgOperand *nvg_evaluate_operand2(struct nvgOperand *op, int operator);
void nvg_evaluate_node(struct Three_AddressNode *node, struct BB *bb);
struct NVG *check_rhs_nvg (struct BB *bb, int rhs);
struct NVG *check_lhs_nvg (struct BB *bb, int lhs);
void add_to_nvg (int lhs, int rhs, int constant, struct BB *bb);
void print_nvg (struct BB *bb);
struct nvgOperand *evaluate_arithmetic(struct nvgOperand *op1, struct nvgOperand *op2, struct Three_AddressNode *node);
int get_next_init_key();
void remove_nvg_lhs(struct BB *bb, int lhs);
void nvg_evaluate_while_node(struct BB *bb, struct Three_AddressNode *node);
void nvg_evaluate_while_block(struct BB *bb);

/* Removing dummies functions */
void removeDummies(struct CFG * cfg);
void removeDummiesBlock(struct BB *block);

/* Global Redundancy Elimination functions */
int is_key_in_rhs(struct expression_tan *expr, int key);
void copy_global_expr_rhs(int *to);
void add_key_to_global_rhs(int key);
void add_line_number_to_expr(struct expression_tan *expr, int line);
void add_expr_to_list(struct BB *block, struct expression_tan *expr);
void remove_expr_from_list(struct BB *block, struct expression_tan *expr);
void gre_evaluate_block(struct BB *bb);
void copy_expr_lines(struct expression_tan *from, struct expression_tan *to);
void copy_expr_rhs(struct expression_tan *from, struct expression_tan *to);
struct expression_tan *copy_expr_to(struct expression_tan *expr, struct BB *block);
void gre_init_with_parent (struct BB *bb);
struct BB * gre_evaluate_blocks(struct BB* bb, int force);
void global_redundancy_elim (struct CFG * cfg);
void expr_combine_lines(struct expression_tan *newNode, struct expression_tan *parent1, struct expression_tan *parent2);
struct replaceTable *lookupGlobalReplacement(int del);
void add_to_global_replace (int del, int rel);
struct expression_tan *lookup_expression(struct BB *bb, struct expression_tan *expr);
char *get_expr_var_name(int hash);
void remove_all_expr_with_key(int key, struct BB *bb);
struct expression_tan *new_expression_tan(char *expr, int LHS, int hash);

/* Cleanup functions */
int remove_unused_variables_block(struct BB *bb);
void cleanup_block(struct BB *bb);
int remove_unused_variables();
void cleanup_nodes();

